package 动态规划;

import java.util.Arrays;

public class 打家劫舍2 {
    //其实就是把环拆成两个队列，一个是从0到n-1，另一个是从1到n，然后返回两个结果最大的。
    public int rob(int[] nums) {
       if (nums.length==1)
           return nums[0];
       if (nums.length==2)
           return Math.max(nums[0],nums[1]);
        int[] a = Arrays.copyOfRange(nums, 0, nums.length - 1);
        int[] b = Arrays.copyOfRange(nums, 1, nums.length);

        return Math.max(method(a),method(b));
    }

    private int method(int[] nums) {
        int[] dp = new int[nums.length+1];
        dp[1] = nums[0];
        for (int i = 2; i < nums.length+1; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return dp[nums.length];
    }
}
